#include "linearList.h"
using namespace std;

void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for (int i = 0; i < curNumberOfItem - 1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem - 1] << endl;
}


void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while (curNode != lastNode)
    {
        if (curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }


        curNode = curNode->next;
    }
}


sequenceList::sequenceList(const int& capacity, const int& initLength, float initArray[])
{
    maxCapcity = capacity;
    curNumberOfItem = 0;
    myList = new float[maxCapcity];
    int initialCount = initLength;
    if (initialCount < 0) initialCount = 0;
    if (initialCount > maxCapcity) initialCount = maxCapcity;
    for (int i = 0; i < initialCount; i++)
    {
        myList[i] = initArray[i];
    }
    curNumberOfItem = initialCount;
}


sequenceList::~sequenceList()
{
    delete[] myList;
    myList = NULL;
    curNumberOfItem = 0;
    maxCapcity = 0;
}


bool sequenceList::addItem(const float& value)
{
    if (curNumberOfItem >= maxCapcity)
        return false;
    myList[curNumberOfItem++] = value;
    return true;
}


bool sequenceList::insertItem(const int& index, const float& value)
{
    if (index < 0 || index > curNumberOfItem)
        return false;
    if (curNumberOfItem >= maxCapcity)
        return false;
    for (int i = curNumberOfItem; i > index; --i)
    {
        myList[i] = myList[i - 1];
    }
    myList[index] = value;
    curNumberOfItem++;
    return true;
}


int sequenceList::deleteItem(const float& value)
{
    int pos = -1;
    for (int i = 0; i < curNumberOfItem; i++)
    {
        if (myList[i] == value)
        {
            pos = i;
            break;
        }
    }
    if (pos == -1)
        return -1;
    for (int i = pos; i < curNumberOfItem - 1; i++)
    {
        myList[i] = myList[i + 1];
    }
    curNumberOfItem--;
    return pos;
}


bool sequenceList::locate(const int& index, float& val)
{
    if (index < 0 || index >= curNumberOfItem)
        return false;
    val = myList[index];
    return true;
}


int sequenceList::locate(const float& value)
{
    for (int i = 0; i < curNumberOfItem; i++)
    {
        if (myList[i] == value)
            return i;
    }
    return -1;
}


void sequenceList::reverse()
{
    for (int i = 0, j = curNumberOfItem - 1; i < j; i++, j--)
    {
        float tmp = myList[i];
        myList[i] = myList[j];
        myList[j] = tmp;
    }
}



listNode::listNode(float nodeData, listNode* succ)
{
    data = nodeData;
    next = succ;
}


listNode::~listNode()
{
}



linkList::linkList()
{
    firstNode = new listNode();
    firstNode->next = NULL;
    curNode = NULL;
    lastNode = firstNode;
    listSize = 0;
}


linkList::linkList(const int& initLength, float initArray[])
{
    firstNode = new listNode();
    firstNode->next = NULL;
    curNode = NULL;
    lastNode = firstNode;
    listSize = 0;
    int count = initLength;
    if (count < 0) count = 0;
    for (int i = 0; i < count; i++)
    {
        tailInsertItem(initArray[i]);
    }
}


linkList::~linkList()
{
    listNode* node = firstNode;
    while (node != NULL)
    {
        listNode* nextNode = node->next;
        delete node;
        node = nextNode;
    }
    firstNode = NULL;
    curNode = NULL;
    lastNode = NULL;
    listSize = 0;
}


bool linkList::headInsertItem(const float& value)
{
    listNode* node = new listNode(value, firstNode->next);
    firstNode->next = node;
    if (listSize == 0)
    {
        lastNode = node;
    }
    listSize++;
    return true;
}


bool linkList::tailInsertItem(const float& value)
{
    listNode* node = new listNode(value, NULL);
    if (listSize == 0)
    {
        firstNode->next = node;
        lastNode = node;
    }
    else
    {
        lastNode->next = node;
        lastNode = node;
    }
    listSize++;
    return true;
}

int linkList::insertItem(const int& index, const float& value)
{
    if (index < 0 || index > listSize)
        return -1;
    listNode* prev = firstNode;
    for (int i = 0; i < index; i++)
    {
        prev = prev->next;
    }
    listNode* node = new listNode(value, prev->next);
    prev->next = node;
    if (prev == lastNode)
    {
        lastNode = node;
    }
    listSize++;
    return index;
}


int linkList::deleteItem(const float& value)
{
    listNode* prev = firstNode;
    listNode* curr = firstNode->next;
    int index = 0;
    while (curr != NULL)
    {
        if (curr->data == value)
        {
            prev->next = curr->next;
            if (curr == lastNode)
            {
                lastNode = prev;
            }
            delete curr;
            listSize--;
            return index;
        }
        prev = curr;
        curr = curr->next;
        index++;
    }
    return -1;
}


bool linkList::locate(const int& index, float& val)
{
    if (index < 0 || index >= listSize)
        return false;
    listNode* curr = firstNode->next;
    for (int i = 0; i < index; i++)
    {
        curr = curr->next;
    }
    val = curr->data;
    return true;
}


int linkList::locate(const float& value)
{
    listNode* curr = firstNode->next;
    int index = 0;
    while (curr != NULL)
    {
        if (curr->data == value)
            return index;
        curr = curr->next;
        index++;
    }
    return -1;
}

void linkList::ascendingOrder()
{
    if (listSize <= 1) return;
    for (listNode* i = firstNode->next; i != NULL; i = i->next)
    {
        listNode* minNode = i;
        for (listNode* j = i->next; j != NULL; j = j->next)
        {
            if (j->data < minNode->data)
                minNode = j;
        }
        if (minNode != i)
        {
            float tmp = i->data;
            i->data = minNode->data;
            minNode->data = tmp;
        }
    }
}

void linkList::reverse()
{
    if (listSize <= 1) return;
    listNode* prev = NULL;
    listNode* curr = firstNode->next;
    listNode* oldFirst = curr;
    while (curr != NULL)
    {
        listNode* nextNode = curr->next;
        curr->next = prev;
        prev = curr;
        curr = nextNode;
    }
    firstNode->next = prev;
    lastNode = oldFirst;
}

void merge(linkList& A, linkList& B)
{
    listNode* pa = A.firstNode->next;
    listNode* pb = B.firstNode->next;


    A.firstNode->next = NULL;
    A.lastNode = A.firstNode;
    A.listSize = 0;


    while (pa != NULL && pb != NULL)
    {
        listNode* take = NULL;
        if (pa->data <= pb->data)
        {
            take = pa;
            pa = pa->next;
        }
        else
        {
            take = pb;
            pb = pb->next;
        }

        take->next = A.firstNode->next;
        A.firstNode->next = take;
        if (A.listSize == 0)
        {
            A.lastNode = take;
        }
        A.listSize++;
    }
    while (pa != NULL)
    {
        listNode* take = pa;
        pa = pa->next;
        take->next = A.firstNode->next;
        A.firstNode->next = take;
        if (A.listSize == 0)
        {
            A.lastNode = take;
        }
        A.listSize++;
    }
    while (pb != NULL)
    {
        listNode* take = pb;
        pb = pb->next;
        take->next = A.firstNode->next;
        A.firstNode->next = take;
        if (A.listSize == 0)
        {
            A.lastNode = take;
        }
        A.listSize++;
    }
    B.firstNode->next = NULL;
    B.lastNode = B.firstNode;
    B.listSize = 0;
}
